package com.zj.leetcode.medium.greed;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: algorithm
 * @description: 用最少数量的箭引爆气球
 * 452 minimum-number-of-arrows-to-burst-balloons
 * @author: Zhang Bo
 * @create: 2022-03-25 11:17:48
 **/
public class MinimumNumberOfArrowsToBurstBalloons {
    public static void main(String[] args) {
//        int[][] points = {{10,16},{-2,8},{1,6},{7,12}};

//        [[1,2],[3,4],[5,6],[7,8]]
//        int[][] points = {{1,2},{3,4},{5,6},{7,8}};

//        [[1,2],[2,3],[3,4],[4,5]]
        int[][] points = {{1,2},{2,3},{3,4},{4,5}};

//        [[-2147483646,-2147483645],[2147483646,2147483647]]
//        int[][] points = {{-2147483646,-2147483645},{2147483646,2147483647}};
        Solution solution = new MinimumNumberOfArrowsToBurstBalloons().new Solution();
        System.out.println(solution.findMinArrowShots(points));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findMinArrowShots(int[][] points) {
            if(points.length <= 1){
                return points.length;
            }
            List<int[]> list =
                    Arrays
                            .stream(points)
                            .sorted((a, b) -> {
                                return Integer.compare(a[0], b[0]);
                            })
                            .collect(Collectors.toList());


            int[] pre = list.get(0);
            int ret = 0;
            for (int i = 1; i < list.size(); i++) {
                if(pre[1] >= list.get(i)[0]){
                    pre[0] = list.get(i)[0];
                    pre[1] = Math.min(pre[1], list.get(i)[1]);
                    if(i == list.size() - 1){
                        ret++;
                    }
                } else {
                    ret++;
                    pre = list.get(i);
                    if(i == list.size() - 1){
                        ret++;
                    }
                }

            }

            return ret;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
